Problem statement: zenit16ckb

Bolo raz jedno akvárium

Počet bodov: 40, časový limit: 2500ms

Korytnačka Žofka si kúpila úžasné nové Megaakvárium 3000. Ako už názov napovedá, toto akvárium má nespočetné množstvo funkcií, ako napr. nastaviteľná teplota vody s presnosťou na stotinu stupňa, nastaviteľná rýchlosť cirkulácie vody, nastaviteľná výška hladiny, …

Akvárium je rozdelené do veľkého množstva do radu usporiadaných komôrok, každá z nich je samostatne konfigurovateľná, rovnako sú ale konfigurovateľné aj akékoľvek súvislé úseky akvária.

Žofka si hneď otvorila internetový prehliadač, aby našla overené dokonalé postupy na kofiguráciu akvária, nech môže pre začiatok vyskúšať niečo, čo fungovalo pre ostatné korytnačky. Ako tak čítala, jej pozornosť upútala jedna zvláštnosť. Každý postup obsahoval veľa napúšťania a vypúštania vody v rôznych úsekoch akvária.

Keďže Žofka by veľmi rada ušetrila na účte za vodu, rada by sa vyhla celému napúšťaniu a vypúšťaniu vody. Preto by potrebovala, aby ste jej raz za čas povedali, aká je hladina v niektorom úseku komôrok. Nakoniec by sa taktiež rada dozvedela stav hladiny v každej komôrke.

Úloha

Komôrky spolu s hladinou vody si predstavíme ako pole celých čísel. Ďalej nám budú chodiť požiadavky štyroch typov:

1. Na úseku od \(a\)-tej komôrky po \(b\)-tu (vrátane) stúpla hladina o \(c\)

2. Na úseku od \(a\)-tej komôrky po \(b\)-tu (vrátane) klesla hladina o \(c\)

3. Aká je najvyššia hladina spomedzi komôrok \(a\) až \(b\)?

4. Aká je najnižšia hladina spomedzi komôrok \(a\) až \(b\)?

Nebude to však také jednoduché. Keď máme prázdnu komôrku a pokúsime sa z nej vypustiť nejaký objem vody, komôrka ostane, pochopiteľne, prázdna. V reči čísel to znamená, že ak by mala hodnota niektorého čísla klesnúť pod \(0\), tak sa zasekne na \(0\).

Vašou úlohou bude teda odsimulovať nalievanie aj vylievanie vody s dolným obmedzením, odpovedať na otázky a nakoniec vypísať pre každú komôrku jej výslednú výšku hladiny. Na začiatku je akvárium prázdne, čiže výška hladiny v každej komôrke je \(0\).

Vstup a výstup

Na prvom riadku dostanete čísla \(n, q\) \((1 \leq n, q \leq 100\,000)\), počet komôrok a počet požiadaviek.

Ďalších \(q\) riadkov vstupu bude obsahovať požiadavky, každá v tvare \(m\ a\ b\ c\) \((1 \leq m \leq 4, 0 \leq a \leq b < n, 0 \leq c \leq 10^{6})\), kde \(m\) označuje číslo požiadavky a zvyšné čísla určujú jej parametre popísané hore. Pre požiadavky tretieho a štvrtého typu bude platiť \(c = 0\).

Pre každú požiadavku tretieho a štvrtého typu vypíšte do samostatného riadka odpoveď. Na konci vypíšte \(n\) čísel oddelených medzerou, výšky hladiny v políčkach od \(0\)-tého po \((n-1)\)-vé.

 Príklad

Input:

10 5
1 4 7 5
1 6 9 7
4 0 9 0
3 0 9 0
2 4 6 11

Output:

0
12
0 0 0 0 0 0 1 12 7 7

Stav komôrok po vykonaní príslušných zmien:

0:

0 0 0 0 0 0 0 0 0 0

1:

0 0 0 0 5 5 5 5 0 0

2:

0 0 0 0 5 5 12 12 7 7

5:

0 0 0 0 0 0 1 12 7 7